﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MatrixMutiply
{
    class Program
    {
        static void MatrixChain(int[] p)
        {
            var n = p.Length - 1;
            var m=new int[n+1,n+1];
            var s=new int[n+1,n+1];
            for (int i = 1; i <= n; i++)
            {
                m[i,i] = 0;
            }
            for (var l = 2; l <= n; l++)
            {
                for (var i = 1; i <= n - l + 1;i++ )
                {
                    var j = i + l - 1;
                    m[i, j] = int.MaxValue;
                    for (var k = i; k <= j - 1; k++)
                    {
                        var q = m[i, k] + m[k + 1, j] + p[i - 1] * p[k] * p[j];
                        if (q < m[i, j])
                        {
                            m[i, j] = q;
                            s[i, j] = k;
                        }
                    }
                }
            }
            Console.WriteLine("m 数组:");
            Print(m);
            Console.WriteLine("s 数组:");
            Print(s);
            Console.WriteLine("最优加全括号:");
            PrintOptimalParens(s,1, 6);
        }

        static void Print(int[,] m)
        {
            for (int i = 1; i <= m.GetUpperBound(0); i++)
            {
                for (int j = 1; j <= m.GetUpperBound(0); j++)
                {
                    Console.Write("m[{0},{1}]:{2} ",i,j,m[i,j]);
                }
                Console.WriteLine();
            }
        }

        static void PrintOptimalParens(int[,] s, int i, int j)
        {
            if (i == j)
            {
                Console.Write(string.Format("A{0}", j));
            }
            else
            {
                Console.Write("(");
                PrintOptimalParens(s, i, s[i, j]);
                PrintOptimalParens(s, s[i, j] + 1, j);
                Console.Write(")");
            }
        }

        static void Main(string[] args)
        {
            //var arr = new int[] { 30, 35, 15, 5, 10, 20, 25 };
            var arr = new int[] { 5, 10, 3, 12, 5, 50, 6 };
            MatrixChain(arr);
            Console.Read();
        }
    }
}
